// https://leetcode.cn/problems/binary-watch/
// Created by ade on 2022/8/4.
//
#include<iostream>
#include<string>
#include<vector>

using namespace std;

class Solution {
public:
    vector <string> readBinaryWatch(int turnedOn) {
        vector <vector<string>> hMap = {
                {"0:"},
                {"1:", "2:", "4:", "8:"},
                {"3:", "5:", "6:", "9:", "10:", "12:"},
                {"7:", "11:"}
        };
        if (turnedOn == 0) return {"0:00"};
        vector <vector<string>> mMap(6, vector < string > {});
        mMap[0] = {"00"};
        for (int i = 1; i < 60; i++) {
            string tmp;
            if (i < 10)
                tmp = "0" + to_string(i);
            else
                tmp = to_string(i);
            mMap[get1Nums(i)].push_back(tmp);
        }
        vector <string> res = {};
        int newTurnedOn = min(3, turnedOn);
        for (int i = 0; i <= newTurnedOn; i++) {
            if(turnedOn - i > 5) continue;
            for (auto h : hMap[i]) {
                for (auto m:mMap[turnedOn - i]) {
                    res.push_back(h + m);
                }
            }
        }
        return res;
    }

    // 1 1 1 1 1 1
    // 59 = 32 + 16 + 8 + 2 + 1 111011
    int get1Nums(int num) {
        int count = 0;
        while (num > 0) {
            if (num % 2 == 1) {
                count++;
                num = (num - 1) / 2;
            } else {
                num = num / 2;
            }
        }
        return count;
    }
};

int main() {
    Solution so;
    auto s = so.readBinaryWatch(1);
    cout << "show:" << endl;
    for (auto i :s) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}